#include<stdio.h>

//二叉树中各节点的数据类型定义
typedef char TreeType;
 
//二叉树中各节点的结构定义
typedef struct TreeNode
{
    TreeType data;//节点的数据域
    struct TreeNode* lchild;//指向左节点的指针
    struct TreeNode* rchild;//指向右节点的指针
}TreeNode;      


/**
 * 与用头结点的指针来表示一个链表类似，这里用根节点的指针来表示一棵树。初始时，树中没有任何结点，
 * 所以将根节点的指针取值置为空即可。因为这里要改变根节点的指针取值，所以，需要传递二级指针作为参数
*/
void TreeInit(TreeNode** root){
    if (root==NULL)
    {
        return;
    }
    *root=NULL;
    return ;
}

//根据先序遍历的结果创建一棵树
//arr为带#的先序序列字符串，size为字符串的长度，index为位置下标，null_flag为空树的标志
TreeNode* _TreeCreate(TreeType arr[],size_t size,size_t* index,char null_flag)
{                                                                                                                                     
    if(arr == NULL ||  size < 0 || index == NULL)
    {
        //非法输入
        return NULL;
    }
    
    if(*index == size)
    {
        //数组已遍历结束,树创建完成
        return NULL;
    }
    if(arr[*index] == null_flag)//null_flag是空树的标志，这里为#
    {
        //空树
        return NULL;
    }
    //创建根节点
    TreeNode* root = CreateNode(arr[*index]);
    (*index)++;
    //递归创建左子树
    root->lchild = _TreeCreate(arr,size,index,null_flag);
    (*index)++;
    //递归创建右子树
    root->rchild = _TreeCreate(arr,size,index,null_flag);
    return root;
}
TreeNode* TreeCreate(TreeType arr[],size_t size,char null_flag)
{
    size_t index = 0;
    TreeNode* root =  _TreeCreate(arr,size,&index,null_flag);
    return root;
}

/**
 * 先序遍历的顺序为：先遍历根节点，然后遍历左子树，最后遍历右子树。在遍历左右子树时，将左右子树再当做一棵树，按照先序遍历的顺序对其进行遍历。所以要对左右子树进行递归遍历。根节点为空时，即为递归出口
*/
//先序遍历树
void PreOrder(TreeNode* root)
{
    if(root == NULL)
    {
        //空树
        printf("# ");//输出#表示空节点                                                                                                
        return;
    }
 
    //输出根节点
    printf("%c ",root->data);
    //递归遍历左子树
    PreOrder(root->lchild);
    //递归遍历右子树
    PreOrder(root->rchild);
    return;
}

/**
 * 与先序遍历类似，在中序遍历时，先递归遍历左子树，然后访问根节点，最后递归遍历右子树。当结点为空时，即到达递归出口
*/
//中序遍历
void InOrder(TreeNode* root)
{
    if(root == NULL)
    {
        //空树
        printf("# ");
        return;
    }
 
    //中序遍历左子树
    InOrder(root->lchild);
    //输出根节点
    printf("%c ",root->data);
    //中序遍历右子树
    InOrder(root->rchild);
    return;
}

//后序遍历
void PostOrder(TreeNode* root)
{
    if(root == NULL)
    {
        //空树
        printf("# ");
        return;
    }
    //后序遍历左子树
    PostOrder(root->lchild);
    //后序遍历右子树
    PostOrder(root->rchild);
    输出根节点
    printf("%c ",root->data);
    return;
}

//层序遍历
void LevelOrder(TreeNode* root)                                                                                                       
{
    if(root == NULL)
    {
        //空树
        return;
    }
 
    //借助队列来完成层序遍历
    SeqQueue queue;//定义一个顺序队列
    SeqQueueInit(&queue);//初始化队列
    
    //1. 将根节点的指针入队列
    SeqQueuePush(&queue,root);
    int ret;
    SeqQueueType front;
    while(1)
    {
        //2. 取队首元素，如果队列为空，说明已经遍历结束
        ret = SeqQueueTop(&queue,&front);
        if(ret == -1)
        {
            //队列已空，树已经遍历完
            break;
        }
   //3. 打印队首元素
        printf("%c ",front->data);
        //4. 队首元素出对列
        SeqQueuePop(&queue);
        //5. 如果队首元素的左右节点非空，则将左右节点的指针入队
        if(front->lchild != NULL)
        {
            SeqQueuePush(&queue,front->lchild);
        }
        if(front->rchild != NULL)
        {
            SeqQueuePush(&queue,front->rchild);
        }
        //6. 循环2.～5.
    }
    return;
}

void DestroyNode(TreeNode* node)
{
    free(node);
    return;
}
 
//void TreeDestroy(TreeNode** root);
//二叉树的销毁(后序遍历销毁)
void TreeDestroy(TreeNode** root)
{
    if(root == NULL)
    {   
        //非法输入
        return;
    }   
    if(*root == NULL)
    {   
        //空树
        return;
    }   
    TreeDestroy(&((*root)->lchild));//销毁左子树
    TreeDestroy(&((*root)->rchild));//销毁右子树
    DestroyNode(*root);//销毁根节点
    *root = NULL;//将销毁的结点置为空
    return;
}

int main(int argc, char const *argv[])
{
    
    return 0;
}
